package com.leetcode.ask;

/**
 * @ProjectName: leetcode
 * @Package: com.leetcode.ask
 * @description: 寻找两个有序数组的中位数
 * 第4题
 * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * @Author: liyc
 * @CreateDate: 2020/1/7 4:34 PM
 * @Version: 1.0
 * <p>Copyright: Copyright (c) 2020</p>
 */
public class FindMedianSortedArrays {


    /**
     * @param
     * @return
     * @description 自己解法
     * 1.将两个数组合并
     * 2.利用快速排序，从小到达重新排序数组
     * 3.如果数组长度为奇数，则取中间的数据
     * 4.如果数组长度为偶数，则取中间的两个数/2
     * @author liyc
     * @date 2020/1/7
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int total[] = new int[nums1.length + nums2.length];
        for (int i = 0; i < nums1.length; i++) {
            total[i] = nums1[i];
        }

        for (int i = nums1.length, j = 0; i < total.length && j < nums2.length; i++, j++) {
            total[i] = nums2[j];
        }

        quickSort(total, 0, total.length - 1);

        if (total.length % 2 == 0) {
            int t = (total[total.length / 2 - 1] + total[total.length / 2]) * 100 / 2;
            double mid = t / 100.00;
            return mid;
        } else {
            return total[total.length / 2] / 1.00;
        }
    }

    /**
     * @param
     * @return
     * @description 快速排序
     * 1.传入数组，开始标记和结束标记位置
     * @author liyc
     * @date 2020/1/7
     */
    public static void quickSort(int[] s, int l, int r) {
        if (l < r) {
            //Swap(s[l], s[(l + r) / 2]);
            //将中间的这个数和第一个数交换
            int i = l;
            int j = r;
            int x = s[l];
            while (i < j) {
                while (i < j && s[j] >= x) {
                    // 从右向左找第一个小于x的数
                    j--;
                }
                if (i < j) {

                    s[i++] = s[j];
                }
                while (i < j && s[i] < x) {
                    // 从左向右找第一个大于等于x的数
                    i++;
                }
                if (i < j) {
                    s[j--] = s[i];
                }
            }
            s[i] = x;
            // 递归调用
            quickSort(s, l, i - 1);
            quickSort(s, i + 1, r);
        }
    }

    public static void main(String[] args) {
        int mums1[] = new int[]{3};
        int mums2[] = new int[]{-2, -1};
        System.out.println(findMedianSortedArrays(mums1, mums2));
//        int arr[] = new int[]{11, 2, 4, 3, 2, 89, 91, 17, 26};
//        quickSort(arr, 0, arr.length - 1);
//        for (int m : arr) {
//            System.out.println(m);
//        }

    }
}
